package com.buddy.leetcode._03;

import java.util.HashSet;

/**
 *  无重复字符的最长子串
 *  给定一个字符串，找出不含有重复字符的最长子串的长度。
 *  示例：
 *  给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
 *  给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
 *  给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。
 *
 */
public class LongestSubstringWithoutRepeatingCharacters {

    public static int myLengthOfLongestSubstring(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        StringBuilder result = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = 0;i<chars.length;i++){
            char str = chars[i];
            if (stringBuilder.indexOf(str+"") < 0){
                stringBuilder.append(str);
            }else{
                if (stringBuilder.length() > result.length()){
                    result = stringBuilder;
                }
                //已经有重复的了。删除吧
                String ss = stringBuilder.toString();
                stringBuilder = new StringBuilder(ss.substring(ss.indexOf(str)+1));
                stringBuilder.append(str);
            }
        }

        if (stringBuilder.length() > result.length()){
            result = stringBuilder;
        }
//        System.out.println(result.toString());
        return result.length();
    }

    public int lengthOfLongestSubstring(String s) {
        int res = 0, left = 0, right = 0;
        HashSet<Character> t = new HashSet<Character>();
        while (right < s.length()) {
            if (!t.contains(s.charAt(right))) {
                t.add(s.charAt(right++));
                res = Math.max(res, t.size());
            } else {
                t.remove(s.charAt(left++));
            }
        }
        return res;
    }
}
